PROJECTENGRAM

[QZ] CSOPESY PRACTICE QUIZ 2 - CPU SCHEDULING

Tags: #◇Computer Science #◇CSOPESY #◇Operating Systems #◇CPU Scheduling #◇Quiz #◇Reviewer

CSOPESY Practice Quiz 2: CPU Scheduling (Weeks 6-8)

◇Overview

This quiz covers CPU Scheduling algorithms and Process Synchronization from Weeks 6 through 8. It is structured as a real exam format: Part I tests conceptual understanding with multiple choice questions, and Part II requires manual Gantt chart construction and metric computation.

Coverage:

  • Note 06: CPU Scheduling (FCFS, SJF, SRTF, Priority, Round Robin, Dispatcher)
  • Note 07: Synchronization Tools (Race Conditions, Mutex, Semaphores, Deadlock)

◇Part I: Problem Solving — CPU Scheduling Gantt Charts

Problem 1: FCFS and Non-Preemptive SJF

Given the following set of processes:

ProcessArrival Time (AT)Burst Time (BT)
P1010
P225
P344
P467

Solve for each algorithm:

  1. Draw the Gantt chart (execution timeline).
  2. Compute Completion Time (CT), Turnaround Time (TAT = CT - AT), and Waiting Time (WT = TAT - BT) for each process.
  3. Compute the Average Waiting Time.

Formulas:
TAT=CT−ATTAT = CT - AT
WT=TAT−BTWT = TAT - BT
Avg WT=∑WTinAvg\ WT = \frac{\sum WT_i}{n}

Problem 2: SRTF and Round Robin (q = 3)

Use the same process table from Problem 1.

For Round Robin with quantum q = 3:

  • Processes arriving at the same time a quantum expires join the queue BEFORE the preempted process is re-queued.
  • Processes with the same remaining time: do not preempt (continue running the current process).

◇Problem Solving Answer Key — Gantt Charts & Metrics

Problem 1 Solution: FCFS

Gantt Chart:

『』
TIMELINE // GANTT
P110ms
0
P25ms
10
P34ms
15
P47ms
19
26

Process Metrics:

ProcessATBTCTTATWT
P101010100
P22515138
P344191511
P467262013

Average Waiting Time: (0+8+11+13)/4=32/4=8.0(0 + 8 + 11 + 13) / 4 = 32 / 4 = \mathbf{8.0} ms

Problem 1 Solution: Non-Preemptive SJF

Selection logic:

  • t=0: Only P1 available → P1 runs (0→10).
  • t=10: P2 (BT=5), P3 (BT=4), P4 (BT=7) all present → shortest is P3 (4) → P3 runs (10→14).
  • t=14: P2 (5), P4 (7) → shortest is P2 (5) → P2 runs (14→19).
  • t=19: Only P4 → P4 runs (19→26).

Gantt Chart:

『』
TIMELINE // GANTT
P110ms
0
P34ms
10
P25ms
14
P47ms
19
26

Process Metrics:

ProcessATBTCTTATWT
P101010100
P225191712
P34414106
P467262013

Average Waiting Time: (0+12+6+13)/4=31/4=7.75(0 + 12 + 6 + 13) / 4 = 31 / 4 = \mathbf{7.75} ms

Problem 2 Solution: SRTF (Preemptive SJF)

Event-by-event trace:

TimeEventRemaining TimesCPU
t=0P1 arrivesP1(10)P1
t=2P2 arrives (5) < P1 rem (8) → preempt P1P1(8), P2(5)P2
t=4P3 arrives (4) > P2 rem (3) → continueP1(8), P2(3), P3(4)P2
t=6P4 arrives (7) > P2 rem (1) → continueP1(8), P2(1), P3(4), P4(7)P2
t=7P2 finishes. Shortest: P3(4)P1(8), P3(4), P4(7)P3
t=11P3 finishes. Shortest: P4(7)P1(8), P4(7)P4
t=18P4 finishes. Only P1 leftP1(8)P1
t=26P1 finishes——

Gantt Chart:

『』
TIMELINE // GANTT
P12ms
0
P25ms
2
P34ms
7
P47ms
11
P18ms
18
26

Process Metrics:

ProcessATBTCTTATWT
P1010262616
P225750
P3441173
P46718125

Average Waiting Time: (16+0+3+5)/4=24/4=6.0(16 + 0 + 3 + 5) / 4 = 24 / 4 = \mathbf{6.0} ms

Problem 2 Solution: Round Robin (q = 3)

Queue trace (format: [Queue] → Run → [Queue after]):

SliceTimeProcessRemaining AfterQueue Before Next
10→3P1P1(7)[P2, P3*, P1] — P2 at t=2, P3 at t=3
23→6P2P2(2)[P3, P4*, P1, P2] — P3 at t=4, P4 at t=6
36→9P3P3(1)[P4, P1, P2, P3]
49→12P4P4(4)[P1, P2, P3, P4]
512→15P1P1(4)[P2, P3, P4, P1]
615→17P2DONE (CT=17)[P3, P4, P1]
717→20P3P3(0) → DONE (CT=20)[P4, P1]
820→23P4P4(1)[P1, P4]
923→26P1P1(1)[P4, P1]
1026→27P4DONE (CT=27)[P1]
1127→28P1DONE (CT=28)—

Gantt Chart:

『』
TIMELINE // GANTT
P13ms
0
P23ms
3
P33ms
6
P43ms
9
P13ms
12
P22ms
15
P33ms
17
P43ms
20
P13ms
23
P41ms
26
P11ms
27
28

Process Metrics:

ProcessATBTCTTATWT
P1010282818
P225171510
P344201612
P467272114

Average Waiting Time: (18+10+12+14)/4=54/4=13.5(18 + 10 + 12 + 14) / 4 = 54 / 4 = \mathbf{13.5} ms

[!note] Takeaway
For this process set: SRTF achieves the best Avg WT (6.0 ms), followed by SJF (7.75 ms), FCFS (8.0 ms), and RR (13.5 ms). SRTF is optimal but requires preemption overhead and future burst knowledge.

◇References & Navigation

CONFIRMATION // 理解度の確認

ACTIVE RECALL VERIFICATION

Select an answer to verify conceptual comprehension and reveal the technical rationale.

Q1

Which CPU scheduling algorithm is provably optimal for minimizing average waiting time among all non-preemptive algorithms?

Q2

A CPU scheduler uses the exponential average formula τn+1=αtn+(1−α)τn\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n to predict future CPU burst lengths. If α=0\alpha = 0, what is the behavior of this predictor?

Q3

Process P1 (burst = 10ms) is currently running. At time t=5, Process P2 arrives with a burst of 3ms. Under the Shortest Remaining Time First (SRTF) algorithm, what happens?

Q4

Which of the following is the primary drawback of FCFS scheduling in a mixed-workload environment?

Q5

In Priority Scheduling, a low-priority process has been waiting in the ready queue for an extremely long time and has never received the CPU. What technique prevents this indefinite starvation?

Q6

Round Robin with a very large time quantum (approaching infinity) behaves like which other scheduling algorithm?

Q7

The time it takes for the OS to stop the current process, save its state, load the next process's state, and hand control to it is called:

Q8

Two threads access a shared counter variable without synchronization. Thread A reads the value (5), Thread B reads the value (5), Thread A increments and writes (6), Thread B increments and writes (6). The final value is 6 instead of the expected 7. What problem does this illustrate?

Q9

A correct solution to the Critical Section Problem must satisfy three conditions. Which of the following is NOT one of them?

Q10

A mutex_lock() call on a mutex that is already held by another thread causes the calling thread to spin in a tight while-loop until the mutex is released. What is this behavior called?

Q11

A Counting Semaphore is initialized to the value 3. Three threads each call wait() (P-operation), acquiring it successfully. A fourth thread calls wait(). What happens to the fourth thread?

Q12

For a deadlock to occur, which of the following four necessary conditions must ALL be present simultaneously?

Q13

Process A holds Resource 1 and is waiting for Resource 2. Process B holds Resource 2 and is waiting for Resource 1. Which deadlock condition does this scenario directly demonstrate?

Q14

Which of the following scheduling criteria should be MINIMIZED to improve system performance?

Q15

A process is currently in the Running state and its time quantum expires. It has not finished its burst. Which state transition occurs next?

[QZ] CSOPESY Practice Quiz 2 - CPU Scheduling | PROJECT ENGRAM